package 代码记录.剑指offer错题本;

/**
 * @author zx
 * @create 2022-05-29 9:35
 */
public class 打印从1到最大的n位数_17 {
    public int[] printNumbers2(int n) {
        int k = (int)Math.pow(10,n);
        int[] res = new int[k - 1];
        for(int i = 0;i < res.length;i++){
            res[i] = i + 1;
        }
        return res;
    }

    /**
     在数字很大的情况下，哪怕long类型也无法承载，那必须要用字符串保存。
     对于本题其实就是对数字0~9的全排列，从1位数0~9的全排列到n位数0~9的全排列，其中要注意的是数字开头不应该有0。
     简单提一下全排列，比如对于数字1，2，3的全排列是：123, 132, 213, 231, 312, 321
     为了能够测试通过，最后把字符串形式变成了int形式，其实应该返回字符串数组
     以下是具体步骤：
     1.为了避免数字开头出现0，先把首位first固定，first取值范围为1~9
     2.用digit表示要生成的数字的位数,本题要从1位数一直生成到n位数,对每种数字的位数都生成一下首位,所以双重for循环
     3.生成首位之后进入递归生成剩下的digit - 1位数，从0~9中取值
     4.递归的中止条件为已经生成了digit位的数字，即index == digit，将此时的数num转为int加到结果res中
     时间复杂度：O(10^n).从1到 10 ^n - 1的数肯定都遍历了一遍
     空间复杂度：O(n),空间复杂度度主要在递归栈及num数组里,递归的最大深度和数组的最大长度都为n;返回值为O(10^n)
     */
    int[] res;
    int count = 0;
    public int[] printNumbers(int n) {
        res = new int[(int)Math.pow(10, n) - 1];
        for(int digit = 1; digit < n + 1; digit++){
            for(char first = '1'; first <= '9'; first++){
                char[] num = new char[digit];
                num[0] = first;
                dfs(1, num, digit);
            }
        }
        return res;
    }
    private void dfs(int index, char[] num, int digit){
        if(index == digit){
            res[count++] = Integer.parseInt(String.valueOf(num));
            return;
        }
        for(char i = '0'; i <= '9'; i++){
            num[index] = i;
            dfs(index + 1, num, digit);
        }
    }
}
